/**
 * Created with IntelliJ IDEA.
 * Description:
 * 判断链表是否为回文链表
 * User: xwl
 */

class ListNode5 {
    int val;
    ListNode5 next;
    ListNode5() {}
    ListNode5(int val) { this.val = val; }
    ListNode5(int val, ListNode5 next) { this.val = val; this.next = next; }
}


public class Test7 {
    // 判断是否是回文链表
    public boolean isPalindrome(ListNode5 head) {
        // 定义俩个节点，分别为快慢指针
        ListNode5 fast = head;
        ListNode5 slow = head;
        // 找到中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 定义一个节点，指向当前翻转节点
        ListNode5 cur = slow.next;
        // 实现翻转
        while (cur != null) {
            // 定义一个节点，记录cur的后一个节点
            ListNode5 curNext = cur.next;
            // 翻转
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 判断
        while (slow != head) {
            if (slow.val != head.val) {
                return false;
            }
            // 讨论偶数时的情况
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
